package org.example.myleet.p1202;

import java.util.*;

public class Solution1 {
    /**
     * 54 ms
     * 用最简单的没有优化过的并查集，结合字母与位置集合的数据结构实现，将同一个连通索引集合中的字符按字典序升序排列并拼接答案
     */
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int[] parent = new int[s.length()];
        for (int i=0; i<parent.length; i++) {
            parent[i] = i;
        }
        //对连通索引构建并查集
        for (List<Integer> pair : pairs) {
            merge(parent, pair.get(0), pair.get(1));
        }
        //找出每个集合的字母以及位置索引
        Map<Integer, CharsPositions> charPosMap = new HashMap<>();
        for (int i=0;i<s.length();i++) {
            int top = find(parent, i);
            CharsPositions charsPositions;
            if (charPosMap.containsKey(top)) {
                charsPositions = charPosMap.get(top);
            } else {
                charsPositions = new CharsPositions();
                charsPositions.chars = new ArrayList<>();
                charsPositions.positions = new ArrayList<>();
            }
            charsPositions.chars.add(s.charAt(i));
            charsPositions.positions.add(i);
            charPosMap.put(top, charsPositions);
        }
        for (CharsPositions charsPositions : charPosMap.values()) {
            charsPositions.chars.sort(Comparator.naturalOrder());
            charsPositions.positions.sort(Comparator.naturalOrder());
        }
        char[] result = new char[s.length()];
        for (CharsPositions charsPositions : charPosMap.values()) {
            for (int i=0;i<charsPositions.positions.size(); i++) {
                result[charsPositions.positions.get(i)] = charsPositions.chars.get(i);
            }
        }
        return new String(result);
    }

    private void merge(int[] parent, int i, int j) {
        parent[find(parent, j)] = parent[find(parent, i)];
    }

    private int find(int[] parent, int i) {
        if (parent[i] != i) {
            parent[i] = find(parent, parent[i]);
        }
        return parent[i];
    }

    static class CharsPositions {
        List<Character> chars;
        List<Integer> positions;
    }
}
